public class CreatTreeByPreorderAndInorder {//根据前序和中序创建二叉树
    public class TreeNode {
        public int val;
        public TreeNode right;
        public TreeNode left;

        public TreeNode(int val) {

            this.val = val;
        }
    }
    class Solution {
        public int preorderindex = 0;//前序遍历的下标
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return buildTreeN(preorder,inorder,0,inorder.length-1);
        }
        public TreeNode buildTreeN(int[] preorder, int[] inorder,int InBegin,int InEnd) {
            if(InBegin>InEnd){
                return null;
            }
            TreeNode root = new TreeNode(preorder[preorderindex]);
            int rootIndex = findVal(inorder,InBegin,InEnd,preorder[preorderindex]);
            preorderindex++;
            root.left = buildTreeN(preorder,inorder,InBegin,rootIndex-1);
            root.right = buildTreeN(preorder,inorder,rootIndex+1,InEnd);
            return root;
        }
        public int findVal(int[] inorder,int inBegen,int inEnd,int val){
            for(int i = inBegen;i<=inEnd;i++){
                if(inorder[i] == val){
                    return i;
                }
            }
            return -1;
        }
    }
}
